package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 1/29/21 11:46 AM
 */
public class _02_打印二叉树的边界节点_01 {

    /**
     *  树的高度与深度相同
     *  树中节点的高度: 从当前节点往下最低的路径的节点个数，为当前节点的高度
     *  树中节点的深度: 从根节点到当前节点的节点数
     *
     * 1.头节点为边界点
     * 2.叶节点为边界点
     * 3.同一层点最左最右的节点为边界点
     * @param root
     */
    public static void printBinaryTreeEdgeNode(TreeNode root) {

        if (root == null) {

            return;
        }

        int height = getHeight(root);

        /**
         * 记录
         */
        TreeNode[][] nodes = new TreeNode[height][2];

        preorderTraversal(root,0,nodes);

        /**
         * 打印左边界
         */
        for (int i = 0; i < height; i++) {
            TreeNode[] nodes2 = nodes[i];
            System.out.println(nodes2[0].val);
        }

        /**
         * 打印不属于上面nodes节点而且是叶子节点的节点
         */
        printNotInNodesAndLeafNode(root,0,nodes);

        /**
         * 打印右边界
         */
        for (int i = height-1; i >= 0; i--) {
            TreeNode[] nodes2 = nodes[i];
            if (nodes2[0] != nodes2[1]) {

                System.out.println(nodes2[1].val);
            }
        }
    }

    public static void printNotInNodesAndLeafNode(TreeNode node,int level,TreeNode[][] nodes) {

        if (node == null) {

            return;
        }

        if (node.left == null && node.right == null && node != nodes[level][0] && node != nodes[level][1]) {

            System.out.println(node.val);
        }
        printNotInNodesAndLeafNode(node.left,level+1,nodes);
        printNotInNodesAndLeafNode(node.right,level+1,nodes);
    }

    public static void preorderTraversal(TreeNode node, int level, TreeNode[][] nodes) {

        if (node == null) {

            return;
        }

        /**
         * 因为是打印边界，只有在开头的是只有左节点或者右节点的时候，nodes[level][0】 === nodes[level][1]，这个跟打印顺序无关
         */
        if (nodes[level][0] == null) {

            nodes[level][0] = node;
        }

        nodes[level][1] = node;

        preorderTraversal(node.left,level + 1,nodes);
        preorderTraversal(node.right,level+ 1,nodes);

    }


    public static int getHeight(TreeNode node) {

        if (node == null) {

            return 0;
        }

        return Math.max(getHeight(node.left),getHeight(node.right)) + 1;
    }


    public static String printBinaryTreeEdgeNodeLevelTraversal(TreeNode root) {


        if (root == null) {

            return "";
        }

        StringBuilder sb = new StringBuilder();
        Stack<TreeNode> stack = new Stack<>();
        Queue<TreeNode> queue = new LinkedList<>();

        int levelCount = 1,levelIndex = 0;

        queue.offer(root);
        while (!queue.isEmpty()) {

            TreeNode node = queue.poll();

            if (node.left != null) {

                queue.offer(node.left);
            }

            if (node.right != null) {

                queue.offer(node.right);
            }

            if (levelIndex == 0) {

                sb.append(node.val).append(",");
            }else if (levelIndex == levelCount - 1) {

                stack.push(node);
            }else if (node.left == null && node.right == null) {

                sb.append(node.val).append(',');
            }

            levelIndex++;

            if (levelIndex == levelCount) {

                levelIndex = 0;
                levelCount = queue.size();
            }
        }

        while (!stack.isEmpty()) {

            sb.append(stack.pop().val).append(",");
        }

        return sb.toString();
    }

    public static void main(String[] args) {

        /**
         *
         *          3
         *        /  \
         *       1    5
         *       \   / \
         *       2  4  6
         *      / \  \
         *    -10 -20 8
         */
        TreeNode root = new  TreeNode(3);

        root.left = new TreeNode(1);
        root.right = new TreeNode(5);
//        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(-10);
        root.left.right.right = new TreeNode(-20);
//        root.left.right.right.right = new TreeNode(-30);
//        root.left.right.right.right.left = new TreeNode(-40);

        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(6);
        root.right.left.right = new TreeNode(8);

    //        printBinaryTreeEdgeNode(root);
        System.out.println(printBinaryTreeEdgeNodeLevelTraversal(root));
    }
}
